What is golomb coding?

Golomb coding is a data compression technique that is used to compress integer numbers with a non-uniform distribution. It is named after Solomon W. Golomb, who introduced the technique back in 1966.

Golomb coding is based on dividing an input integer into two parts: a quotient q and a residue r. The quotient represents the number of times a pre-defined value (called the divisor) goes into the input integer, and the residue represents the remainder that is left over. By encoding the quotient and residue separately, Golomb coding can compress integers with a non-uniform distribution more efficiently than other compression techniques.

There are different variants of Golomb coding, including Rice coding and Elias gamma coding. Rice coding is a variant where the divisor is a power of two, and Elias gamma coding is a variant where the divisor is always one. Both variants have different trade-offs in terms of compression efficiency and encoding/decoding complexity.

Golomb coding is widely used in different applications, such as image and video compression, lossless data compression, and data storage. It is also used in some communication protocols, such as the Compact Noisy Channel Encoding (CNCE) protocol for wireless communication.